package graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CourseSchedule207 {
    @Test
    public void test() {
        canFinish(2, new int[][]{new int[]{0, 1}, new int[]{1, 0}});
        canFinish(2, new int[][]{new int[]{1, 0}});
        canFinish(5, new int[][]{new int[]{1, 4}, new int[]{2, 4}, new int[]{3, 1}, new int[]{3, 2}});
    }

    // 一次遍历中, 一个visited只能判断是否已经遍历过, 但无法判断是否有环.
    // 比如菱形依赖, 3->1->4, 3->2->4, 从第一条到4后, 4就被visited了, 但并没有环啊.
    // 所以要单独用一个path, 回溯记录搜索路径.
    // 可行的优化, 可以将visitedCurrent/path 整合到一个变量int, 用三种不同的值来表示, shit, 好像可以.
    // visitedTotal变量被删除了
    public boolean canFinish(int n, int[][] pr) {
        List<List<Integer>> g = buildGraph(n, pr);

        // 在所有遍历中, 已经被访问过了
        boolean[] visited = new boolean[n];

        // 当前这轮遍历的路径, 需要回溯
        boolean[] path = new boolean[n];

        Arrays.fill(visited, false);

        // 可能有多个起点, 每个都访问一遍, 不然就遍历少了
        boolean can = true;
        for (int i = 0; i < n; i++) {
            // 避免重复访问
            if (!visited[i]) {
                if (!traverseAndCheckCircle(i, path, visited, g)) {
                    System.out.format("circle from i: %d\n", i);
                    can = false;
                    break;
                }
            }
        }
        System.out.format("n: %d, g: %s, can: %s\n", n, g, can);
        return can;
    }

    // 递归遍历所有节点, 记录是否被访问
    public boolean traverseAndCheckCircle(int index, boolean[] path, boolean[] visited, List<List<Integer>> g) {
        if (path[index]) {
            // 发现环了
            return false;
        }
        if (visited[index]) {
            // 已经被访问过了, 不能重复访问. 所以直接返回"无环".
            return true;
        }
        // 标记被访问
        visited[index] = true;
        // 加入到路径中
        path[index] = true;
        for (Integer next: g.get(index)) {
            if (!traverseAndCheckCircle(next, path, visited, /*visitedTotal,*/ g)) {
                return false;
            }
        }
        // 回溯, 从路径中删除
        path[index] = false;
        return true;
    }

    // 先建立邻接表
    public List<List<Integer>> buildGraph(int n, int[][] pr) {
        List<List<Integer>> g = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>(n));
        }
        for (int[] edge : pr) {
            g.get(edge[0]).add(edge[1]);
        }
        return g;
    }
}
